package cn.com.forever.array;

/*
    给定一个数组，请你编写一个函数，返回该数组排序后的形式。
 */

public class ArraySort {
    public static void main(String[] args) {
        int[] array = {2,6,4,8,1,10,34,7,5};
        Insertsort(array);
        //SelectSort(array);
        //BubbleSort(array);

        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
        }
    }

    //插入排序
    //例如要将数组arr=[4,2,8,0,5,1]排序，可以将4看做是一个有序序列，将[2,8,0,5,1]看做一个无序序列。无序序列中2比4小，于是将2插入到4的左边，此时有序序列变成了[2,4]，
    // 无序序列变成了[8,0,5,1]。无序序列中8比4大，于是将8插入到4的右边，有序序列变成了[2,4,8],无序序列变成了[0,5,1]。
    // 以此类推，最终数组按照从小到大排序。该算法的时间复杂度为O(n^2)。
    public static int[] Insertsort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i-1;
            while(j>=0 && temp < arr[j]){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
        return arr;
    }


    //选择排序
    //每一个与后面所有的作比较，小的放前面
    public static int[] SelectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    //冒泡排序
    //每一个与相邻作比较，确定最大的放最后面
    public static int[] BubbleSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i -1; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }
}
